'''
活动选择问题
    假设有n个活动,这些活动要占用同一片场地,而场地在某时刻只能供一个活动使用

    每个活动都有一个开始时间si和结束时间fi(题目中时间以整数表示),表示活动在[si,fi)区间占用场地

    问:安排哪些活动能够使该场地举办的活动的个数最多
    i    1 2 3 4 5 6 7   8  9  10 11
    si   1 3 0 5 3 5 6   8  8  2  12
    fi   4 5 6 7 9 9 10  11 12 14 16

    贪心结论:最先结束的活动一定是最优解的一部分

    证明:假设a是所有活动中最先结束的活动,b是最优解中最先结束的活动.

        如果a = b,结论成立

        如果a != b ,则b的结束时间一定晚于a的结束时间,则此时用a替换掉最优解中的b,
        a一定不与最优解中的其他活动时间重叠,因此替换后的解压实最优解

'''
activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
activities.sort(key = lambda x : x[1])
print(activities)

def func(activities):
    act = []
    act.append(activities[0])
    for i,(start,end) in enumerate(activities):
        if i >0 and start >= act[-1][1]:
            act.append(activities[i])
        else:
            continue
    return act

print(func(activities))